package cn.fansunion.leecode.array;

/**
 * 找到数组的中间位置
 * 给你一个下标从 0 开始的整数数组 nums ，请你找到 最左边 的中间位置 middleIndex （也就是所有可能中间位置下标最小的一个）。

中间位置 middleIndex 是满足 nums[0] + nums[1] + ... + nums[middleIndex-1] == nums[middleIndex+1] + nums[middleIndex+2] + ... + nums[nums.length-1] 的数组下标。

如果 middleIndex == 0 ，左边部分的和定义为 0 。类似的，如果 middleIndex == nums.length - 1 ，右边部分的和定义为 0 。

请你返回满足上述条件 最左边 的 middleIndex ，如果不存在这样的中间位置，请你返回 -1 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-middle-index-in-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author wen.lei@brgroup.com
 *
 *         2022-1-20
 */
public class FindTheMiddleIndexInArray {

    public int findMiddleIndex(int[] nums) {
        return -1;
    }
    
    //若干用例不通过，很尴尬
    public int findMiddleIndexError(int[] nums) {
        if (nums == null || nums.length < 1) {
            return -1;
        }
        if (nums.length == 1) {
            return 0;
        }
        int leftSum = 0;
        int rightSum = 0;
        for (int index = 0; index < nums.length - 1; index++) {
            leftSum = sum(nums, 0, index + 1);
            rightSum = sum(nums, index + 2, nums.length);
            if(index==0) {
                leftSum=0;
                rightSum = sum(nums, index + 1, nums.length);
                if(leftSum==rightSum) {
                    return index;
                }
            }else if(index == nums.length-1) {
                rightSum=0;
                leftSum = sum(nums, 0, index+1);
                if(leftSum==rightSum) {
                    return nums.length-1;
                }
            }
            if (leftSum == rightSum) {
                return index + 1;
            }
        }
        return -1;
    }

    private int sum(int[] nums, int left, int right) {
        int sum = 0;
        for (int index = left; index < right; index++) {
            sum += nums[index];
        }
        return sum;
    }

    /**
     * 最早的思路，陷入“魔怔”中了，想着一次for循环或者O(n)就搞定
     * 
     * @param nums
     * @return
     */
    public int findMiddleIndexError2(int[] nums) {
        if (nums == null || nums.length < 1) {
            return -1;
        }
        if (nums.length == 1) {
            return 0;
        }
        int leftIndex = 0;
        int rightIndex = nums.length - 1;
        int leftSum = nums[leftIndex];
        int rightSum = nums[rightIndex];
        while (leftIndex < rightIndex - 1) {
            if (rightSum >= leftSum) {
                leftIndex++;
                if (leftIndex < rightIndex - 1) {
                    leftSum += nums[leftIndex];
                }
            } else if (rightSum < leftSum) {
                rightIndex--;
                if (leftIndex < rightIndex - 1) {
                    rightSum += nums[rightIndex];
                }
            }
        }
        if (leftSum == rightSum) {
            return leftIndex + 1;
        }
        return -1;

    }

}
